#include "SplayTree.h"

struct TreeNode {
    ElementType data;
    struct TreeNode *left, *right;
    struct TreeNode* parent;  //记录节点的父节点，便于算法实现
};

static Position FindWhere(SplayTree, ElementType, Position);
static Position LRotate(Position p);
static Position RRotate(Position p);
static Position LLRotate(Position p);
static Position RRRotate(Position p);
static Position LRRotate(Position p);
static Position RLRotate(Position p);
static SplayTree RemoveRoot(SplayTree tree);

//找到数据位置，分为两种情况：
// 1、树中不存在的数据：返回待插入位置的父节点
// 2、树种存在的数据：返回数据的位置
static Position FindWhere(SplayTree tree, ElementType data, Position parent) {
    if (!tree)
        return parent;
    if (data == tree->data)
        return tree;
    else if (data < tree->data)
        return FindWhere(tree->left, data, tree);
    else
        return FindWhere(tree->right, data, tree);
}

//返回最后完成插入的树，旨在处理树为空的情形
SplayTree Insert(SplayTree tree, ElementType data) {
    //如果tree为空，则整个树为空树，新建根节点返回即可
    if (!tree) {
        Position p = (Position)malloc(sizeof(struct TreeNode));
        p->data = data;
        p->parent = NULL;
        p->left = NULL;
        p->right = NULL;
        return p;
    }

    //如果tree不为NULL，则查找该数据；tree不为空，res不可能为NULL，不做判断
    Position res = FindWhere(tree, data, NULL);

    Position newNode = (Position)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->parent = res;

    // tree为空，返回该节点
    if (!res)
        return newNode;

    // res非空，存在两种情况：有该数据返回该数据、无该数据返回其父
    if (res->data != data) {
        if (data < res->data)
            res->left = newNode;
        if (data > res->data)
            res->right = newNode;
    }
    return tree;
}

//同常规二叉搜索树
void MakeEmpty(SplayTree tree) {
    if (tree) {
        MakeEmpty(tree->left);
        MakeEmpty(tree->right);
        free(tree);
    }
}

///////////////////////////////////////////////////////////////////////////////////
//单次旋转的功能函数
static Position LRotate(Position p) {
    Position A = p, B = A->left, E = B->right;
    B->parent = p->parent;
    B->right = A;
    A->parent = B;
    A->left = E;

    if (E)
        E->parent = A;
    return B;
}
static Position RRotate(Position p) {
    Position A = p, C = A->right, F = C->left;
    C->parent = p->parent;
    C->left = A;
    A->parent = C;
    A->right = F;
    if (F)
        F->parent = A;
    return C;
}
static Position LLRotate(Position p) {
    Position A = p, B = A->left, D = B->left, E = B->right, I = D->right;
    D->parent = p->parent;
    D->right = B;
    B->parent = D;
    B->left = I;
    B->right = A;
    A->parent = B;
    A->left = E;

    if (I)
        I->parent = B;
    if (E)
        E->parent = A;
    return D;
}
static Position RRRotate(Position p) {
    Position A = p, C = A->right, D = C->left, E = C->right, F = E->left;
    E->parent = p->parent;
    E->left = C;
    C->parent = E;
    C->left = A;
    C->right = F;
    A->parent = C;
    A->right = D;
    if (F)
        F->parent = C;
    if (D)
        D->parent = A;
    return E;
}
static Position LRRotate(Position p) {
    Position A = p, B = A->left, C = B->right, F = C->left, G = C->right;
    C->parent = p->parent;
    C->left = B;
    C->right = A;
    B->parent = C;
    B->right = F;
    A->parent = C;
    A->left = G;

    if (F)
        F->parent = B;
    if (G)
        G->parent = A;
    return C;
}
static Position RLRotate(Position p) {
    Position A = p, B = A->right, C = B->left, F = C->left, G = C->right;
    C->parent = p->parent;
    C->left = A;
    C->right = B;
    A->parent = C;
    A->right = F;
    B->parent = C;
    B->left = G;

    if (F)
        F->parent = A;
    if (G)
        G->parent = B;
    return C;
}

Position AdjustTree(SplayTree tree, Position node) {
    // tree为空返回NULL
    if (!tree)
        return NULL;

    //如果node==tree，不调整，返回tree
    if (tree == node)
        return tree;

    //如果不是以上情况，则需要自下往上迭代调整
    Position temp = node;
    while (temp) {
        Position C = temp, B = C->parent, A = B->parent;

        //单旋转情况
        if (!A) {
            // L
            if (C == B->left)
                return LRotate(B);
            // R
            if (C == B->right)
                return RRotate(B);
        }
        //多旋转情况
        // LL
        if (B == A->left && C == B->left) {
            if (A == tree)
                return LLRotate(A);

            Position parent = A->parent;
            if (A == A->parent->left) {
                parent->left = LLRotate(A);
                temp = parent->left;
            } else {
                parent->right = LLRotate(A);
                temp = parent->right;
            }
        }
        // RR
        if (B == A->right && C == B->right) {
            if (A == tree)
                return RRRotate(A);

            Position parent = A->parent;
            if (A == A->parent->left) {
                parent->left = RRRotate(A);
                temp = parent->left;
            } else {
                parent->right = RRRotate(A);
                temp = parent->right;
            }
        }
        // LR
        if (B == A->left && C == B->right) {
            if (A == tree)
                return LRRotate(A);

            Position parent = A->parent;
            if (A == A->parent->left) {
                parent->left = LRRotate(A);
                temp = parent->left;
            } else {
                parent->right = LRRotate(A);
                temp = parent->right;
            }
        }
        // RL
        if (B == A->right && C == B->left) {
            if (A == tree)
                return RLRotate(A);

            //注意：此处要暂存parent的值，因为旋转操作后，A的位置已经发生变化，其父节点也发生了变化！！！
            Position parent = A->parent;
            if (A == A->parent->left) {
                parent->left = RLRotate(A);
                temp = parent->left;
            } else {
                parent->right = RLRotate(A);
                temp = parent->right;
            }
        }
    }
}

//这些操作需要伸展操作，调用形式：tree=AdjustTree(tree);
// node为局部操作的顶节点
SplayTree Delete(SplayTree tree, ElementType data) {
    Position where = FindWhere(tree, data, NULL);
    if (!where)
        return tree;
    if (where->data != data)
        return tree;
    tree = AdjustTree(tree, where);

    //删除根节点即可
    tree = RemoveRoot(tree);

    return tree;
}

static SplayTree RemoveRoot(SplayTree tree) {
    if (!tree)
        return NULL;

    if (!tree->left && !tree->right) {
        free(tree);
        return NULL;
    }

    if (tree->right) {
        //用右子树最小值代替根节点
        Position temp = tree->right, minNode = tree->right;
        while (temp) {
            minNode = temp;
            temp = temp->left;
        }
        tree->data = minNode->data;
        if (minNode->right) {
            Position oldNode = minNode->right;
            minNode->data = oldNode->data;
            minNode->right = NULL;
            free(oldNode);
        } else {
            Position oldNode = minNode;
            oldNode->parent->left = NULL;
            free(oldNode);
        }
    } else {
        //用左子树最大值代替根节点
        Position temp = tree->left, maxNode = tree->left;
        while (temp) {
            maxNode = temp;
            temp = temp->right;
        }
        tree->data = maxNode->data;
        if (maxNode->left) {
            Position oldNode = maxNode->left;
            maxNode->data = oldNode->data;
            maxNode->left = NULL;
            free(oldNode);
        } else {
            Position oldNode = maxNode;
            oldNode->parent->right = NULL;
            free(oldNode);
        }
    }

    return tree;
}

//搜索后旋转
Position FindMax(SplayTree tree) {
    if (!tree)
        return NULL;
    Position res = tree;
    Position temp = tree;
    while (temp) {
        res = temp;
        temp = temp->right;
    }
    // temp为最大值
    tree = AdjustTree(tree, res);

    return res;
}

//搜索后旋转
Position FindMin(SplayTree tree) {
    if (!tree)
        return NULL;
    Position res = tree;
    Position temp = tree;
    while (temp) {
        res = temp;
        temp = temp->left;
    }
    // temp为最大值
    tree = AdjustTree(tree, res);

    return res;
}

//搜索后旋转
Position Find(SplayTree tree, ElementType data) {
    //采用内部链接方法查找该节点：NULL表示树为空；有该数据则返回该节点；无该数据则返回其父。
    Position where = FindWhere(tree, data, NULL);
    if (!where)
        return NULL;
    if (where->data != data)
        return NULL;

    //余下情况为有该数据的情况,进行处理即可
    tree = AdjustTree(tree, where);

    return where;
}
///////////////////////////////////////////////////////////////////////////////////

//同常规BST
void PreOrder(SplayTree tree) {
    if (tree) {
        printf("%d\t", tree->data);
        PreOrder(tree->left);
        PreOrder(tree->right);
    }
}

//同常规BST
void InOrder(SplayTree tree) {
    if (tree) {
        InOrder(tree->left);
        printf("%d\t", tree->data);
        InOrder(tree->right);
    }
}

//同常规BST
void PostOrder(SplayTree tree) {
    if (tree) {
        PostOrder(tree->left);
        PostOrder(tree->right);
        printf("%d\t", tree->data);
    }
}

void testSplayTree() {
    SplayTree tree = NULL;
    int arr[15] = {7, 6, 5, 4, 3, 2, 1};
    for (int i = 0; i < 7; i++) {
        tree = Insert(tree, arr[i]);
    }
    printf("\n");
    PreOrder(tree);
    printf("\n");
    InOrder(tree);
    printf("\n");
    PostOrder(tree);

    tree = Find(tree, 1);
    printf("\n");
    PreOrder(tree);
    printf("\n");
    InOrder(tree);
    printf("\n");
    PostOrder(tree);

    /*
    tree = Find(tree, 4);
    printf("\nFind(4)=%d\n", tree->data);
    tree = FindMax(tree);
    printf("\nFindMax()=%d\n", tree->data);
    tree = FindMin(tree);
    printf("\nFindMin()=%d\n", tree->data);
    */

    MakeEmpty(tree);
}

/*
# 每次编译指点修改OTHERH和OTHERC变量即可
OTHERH=SplayTree.h
OTHERC=SplayTree.c

main: main.o other.o
        gcc -o main main.o other.o
        ./main

main.o:

other.o: $(OTHERC) $(OTHERH)
        gcc -c $(OTHERC) -o $@

clean:
        rm -f main *.o

run:
        make
        ./main
*/